
\documentclass[12pt,a4paper]{article}

\usepackage[utf8x]{inputenc}
\usepackage [czech]{babel}

\usepackage[pdftex]{graphicx}

\def\us{\char`\_}

\oddsidemargin=-5mm
\evensidemargin=-5mm
\marginparwidth=.08in
\marginparsep=.01in
\marginparpush=5pt
\topmargin=-15mm
\headheight=12pt
\headsep=25pt
\footskip=30pt
\textheight=25cm
\textwidth=17cm
\columnsep=2mm
\columnseprule=1pt
\parindent=15pt
\parskip=2pt

\begin{document}

\begin{center}
\bf Semestrální projekt PAR 2009/2010:\\[5mm]
    Paralelní algoritmus pro řešení uzlového pokrytí\\[5mm] 
       Zdeněk Papež\\
       Tomáš Kianička\\[2mm]
K336 FEL ČVUT, Karlovo nám. 13, 121 35 Praha 2\\[2mm]
\today
\end{center}

\section{Definice problému a popis sekvenčního algoritmu}

\par
Problém uzlového pokrytí má v neorientovaném grafu $G(V,E)$ o $n$ uzlech a stupni nejvýše $k$ najít minimální uzlové pokrytí. Minimálním uzlovým pokrytím je taková podmnožina uzlů $C$, která pokrývá každou hranu z $E$. Neboli každá hrana z $E$ je incidentní alespoň s jedním uzlem z $C$.

\subsection*{Vstupní data}
\par
$n$ - počet uzlů, přiřozené číslo, $n \geq 5$. \\
$k$ - maximální stupeň uzlu v $G$.\\
$G(V,E)$ - neorientovaný, neohodnocený graf\\

\par
Graf $G$ je načítán z matice sousednosti, která je v souboru, který se předává programu jako parametr. Soubor obsahuje na prvním řádku počet uzlů $n$ a dále pak samotnou matici sousednosti. Jednotlivé hodnoty matice (0,1) jsou oddělenny mezerami. Vstupní formát odpovídá výstupu programu \texttt{Generator}, který pro tento účel využíváme.

\subsubsection*{Ukázka formátu vstupního souboru}

\noindent
\texttt{6\\
0 1 0 0 0 0 \\
1 0 1 0 1 0 \\
0 1 0 1 0 0 \\
0 0 1 0 1 1 \\
0 1 0 1 0 0 \\
0 0 0 1 0 0 
}



\subsection*{Výstup programu}
Výstupem programu je popis stavu výpočtu a jeho řešení. Řešení vždy existuje a je jím minimální podmnožina uzlů $C$ vstupního grafu.


\subsection*{Popis sekvenčního algoritmu}
\par
Sekvenční algoritmus je typu DFS s omezenou hloubkou prohledávaného prostoru. Omezením je triviální horní mez, která je stanovena na $ min(n-1, \lceil \frac{e}{2} \rceil )$. Toto je iniciální nastavení hloubky, do které se prohledává. Hodnota se ale při nalezení kratšího řešení sníží právě na délku tohoto řešení, aby algoritmus již nehledal horší řešení, než dosud nalezené. Pokud algoritmus objeví optimální řešení, neboli řešení délky těsné dolní meze, okamžitě končí a vrací optimální řešení. Těsná dolní mez je minimální počet uzlů, jejichž součet stupňů je roven alepoň počtu hran $E$.

\par
Strom stavového prostoru obsahuje ve svých uzlech uzly grafu a cesta sestupu mezi kořenem a listy určuje kombinaci, která je testována jako podmnožina $C$. Návrat se provádí pokud bylo doraženo aktuální maximální hloubky prohledávání. Pro provádění expanze jsme si zvolili postup, kdy se přidávají uzly nejdříve s nejvyšším stupněm. Nikdy neexpandujeme do uzlu, který by měl nižší stupeň než ten, který je v kombinaci, která je kandidátem na řešení, již obsažen. To nám zaručuje prořezání stromu tak, aby se nezkoušely permutace, ale kombinace. Tedy algoritmus nebude zkoušet řešení \textit{1-2-3}, pokud již dříve testoval například \textit{1-3-2}. Vzniklý strom stavového prostoru je silně nevyvážený - uzel vlevo má vždy o následníka více než uzel vpravo.


\subsection*{Naměřená data sekvenčního algoritmu}

\par
Při testování jsme pracovali se třemi instancemi, které měly sekvenční běh kolem 10 minut. Instance byly rozměru $30\times30$ s $k=10$, $29\times29$ s $k=20$ a $29\times29$ s $k=28$.

\begin{table}[ht]
\centering
\begin{tabular}{c c}
instance & čas [s] \\
\hline
k10 & 557 \\
k20 & 636 \\
k28 & 748 \\
\hline
\end{tabular}

\caption{Tabulka sekvenčních běhů}
\end{table}



\section{Popis paralelního algoritmu a jeho implementace v MPI}


\subsection*{Počáteční rozdělení práce}

O rozdělení práce se stará proces $0$. Proces provede několik počátečních expanzí, aby měl na zásobníku dostatek práce, kterou je možno přidělit ostatním procesům. Pro každý z uzlů, který proces expanzí získal, spočte funkcí \texttt{workload()} počet expanzí, který daný uzel obsahuje ve svém podstromu. Jinými slovy určí pro každý uzel jeho výpočetní zátěz. Zátěž se pro uzly ve stejné hloubce kvůli nevyváženosti stromu značně liší. Podle spočtené záteže se proces $0$ pokusí co nejrovnoměrněji přidělit uzly všem procesům, včetně sebe.


\subsection*{Výpočetní cyklus}
Základním krokem iteračního cyklu je výběr uzlu ze zásobníku, kontrola řešení a další expanze. Jednou za \texttt{CHECK\us MSG\us AMOUNT} iterací nebo v případě že není práce dochází ke kontrole příchozích zpráv. Při měření byla tato konstanta nastavena na hodnotu 100.
\par
Typy zpráv, které v řešení existují jsou:
\begin{itemize}
\item zpráva o nalezení optimálního řešení \texttt{TAG\us OPTIMUM},
\item zpráva informující o snížení hloubky prohledávání \texttt{TAG\us NEW\us UPPER\us BOUND},
\item žádost o práci \texttt{TAG\us WORK\us REQUEST},
\item zpráva s novou prací \texttt{TAG\us SENDING\us WORK},
\item zpráva s peškem \texttt{TAG\us SENDING\us TOKEN} a
\item zpráva pro sběr nejlepšího řešení \texttt{TAG\us COLLECTING\us RESULT}.
\end{itemize}

\par
Přijde-li zpráva o nalezení optimálního řešení, proces skončí. Pouze ten proces, který optimální řešení nalezl, ještě před svým ukončením vypíše znění řešení.
\par
Při obdržení zprávy s novou hloubkou prohledávání si příjemce tuto novou hodnotu nastaví do \texttt{upperBound} a již nebude expandovat do hloubky, která by tuto mez překročila.


\subsection*{Dynamické přerozdělování práce}
\par
Dynamické přerozdělování práce využívá lokální ukazatele na vhodného dárce. Proces zkouší žádat v logickém kruhu procesy s vyšším id, než je on sám. Odpoveď s prací je tedy posílána v opačném směru, což znamená, že po poslání práce si proces nastavuje svoji barvu na černou, čehož se využívá v modifikovaném ADUV. Maximální počet žádostí, pokud dárci odpovídají, že již nemají práci, je nastaven v \texttt{MAX\us WORK\us REQUESTS}. Při testování byl nastaven na hodnotu $5$.

\par
Na zprávu s žádostí o práci proces odpovídá zprávou typu \texttt{TAG\us SENDING\us WORK}. Zpráva je prázdná, pokud již proces nemá práci, nebo nemá-li proces dostatek práce, tedy má méně než je hodnota \texttt{MIN\us WORK\us SIZE}. Tato konstanta byla pro testování rovna $100$. Pokud má dárce dostatek práce, pak zpráva s prací obsahuje přibližně spodní polovinu zásobníku dárcovského procesu. Spodní polovina zásobníku je volena proto, že tyto uzly představují v nevyváženém stromu více práce a protože tyto uzly jsou v menší hloubce.


\subsection*{Ukončení práce a sběr výsledku}

\par
Proces $0$ při skončení práce (v případě že nesehnal dárce práce) zahájí posílání peška. Pokud některý z dalších procesů ještě pracuje, peška přijme, ale ponechá si ho do té doby, než svou práci dokončí. Před přeposláním peška každý proces peška případně obarví načerno, pokud někdy během výpočtu posílal práci. Po dokončení logického kruhu proces $0$ zkontroluje barvu peška a případně odstartuje ještě jedno kolo. Po správném oběhnutí bílého peška proces $0$ pošle zprávu \texttt{TAG\us COLLECTING\us RESULT}, do které vloží své nejlepší nalezené řešení. Každý proces obsah této zprávy zkontroluje a pokud sám našel lepší řešení, než které je ve zprávě uvedeno, nahradí jej, zprávu přepošle dále a skončí. Po dokončení logického kruhu tak proces $0$ obdrží znění nejlepšího řešení, které vypíše a skončí.





\section{Naměřené výsledky a vyhodnocení}



\begin{table}[ht]
\centering
\begin{tabular}{l | c c c c}
 & 1 & 2 & 4 & 8 \\
\hline
k10 & 557 & 224,76 & 115,88 & 64,59\\
k20 & 636 & 307,06 & 157,52 & 78,65\\
k28 & 748 & 435,42 & 188,68 & 94,21\\
\hline
\end{tabular}

\caption{Doba paralelního výpočtu $T(n,p)$ s Infiniband}
\end{table}



\begin{table}[ht]
\centering
\begin{tabular}{l | c c c c}
 & 1 & 2 & 4 & 8 \\
\hline
k10 & 1 & 2,47 & 4,80 & 8,62\\
k20 & 1 & 2,07 & 4,03 & 8,08\\
k28 & 1 & 1,71 & 3,96 & 7,93\\
\hline
\end{tabular}

\caption{Paralelní zrychlení $S(n,p)$ s Infiniband}
\end{table}

\par
Jak již bylo zmíněno v sekci popisující sekvenční výpočet, vybírali jsme takové instance grafů, jejichž sekvenční výpočet trvá přibližně $10$ minut. Názvy instancí jsou k10, k20 a k28, kde číslo označuje nejvyšší stupeň uzlu grafu. Následující tabulky ilustrují časy běhů paralelního algoritmu $T(n,p)$ a zrychlení $S(n,p)$ pro tyto instance při použití dvou odlišných komunikačních rozhraní: Infiniband a Ethernet. 





\par
Jak z tabulek, tak z grafů je zřejmé, že zrychlení paralelního algoritmu je zvláště pro instanci k10 superlineární. Tuto vlastnost přisuzujeme chování paralelního algoritmu, kdy se v případě nalezení dosud nejlepšího řešení posílá nová horní mez zprávou \texttt{TAG\us NEW\us UPPER\us BOUND} a tím se omezuje hloubka prohledávání u všech procesů.


\par
Z naměřených hodnot je také patrné, že díky výpočtu pracovní zátěže a vcelku rovnoměrnému rozdělení práce výrazně snižuje komunikační zátěž. Díky tomu, a také díky velice nízkým velikostem přenášených zpráv, nedochází k význačnému rozdílu naměřených časů v případě použití komunikačního rozhraní Infiniband a Ethernet. 


\begin{table}[htbc]
\centering
\begin{tabular}{l | c c c c}
 & 1 & 2 & 4 & 8 \\
\hline
k10 & 557 & 230,8 &       &   \\
k20 & 636 & 319,8 & 155,4 & 77,8\\
k28 & 748 &       & 183 &    \\
\hline
\end{tabular}

\caption{Doba paralelního výpočtu $T(n,p)$ s Ethernet}
\end{table}



\begin{table}[htbc]
\centering
\begin{tabular}{l | c c c c}
 & 1 & 2 & 4 & 8 \\
\hline
k10 & 1 & 2,41 &       &   \\
k20 & 1 & 1,98 & 4,09 & 8,17\\
k28 & 1 &       & 4,08 &    \\
\hline
\end{tabular}

\caption{Paralelní zrychlení $S(n,p)$ s Ethernet}
\end{table}



\par
Úplné výsledky pro počet procesorů 1,2,4,8 se nám podařilo získat pouze u spuštění s Infiniband. Při komunikaci přes Ethernet nám z neznámých důvodů některé instance na jistých počtech procesorů končily chybou. Z těchto důvodů v grafech uvádíme jen reprezentaci výsledků pro Infiniband.



\begin{figure}[tb]
\begin{center}
\includegraphics{cas_infiniband}
\caption{Graf časů výpočtu pro Infiniband}
\label{cas_infiniband}
\end{center}
\end{figure}




\begin{figure}[tb]
\begin{center}
\centering
\includegraphics{infiniband}
\caption{Graf zrychlení pro Infiniband}
\label{cas_infiniband}
\end{center}
\end{figure}






\subsection*{Komunikační náročnost algoritmu}

\par
Výpočet komunikační náročnosti můžeme díky zanedbatelné velikosti posílaných zpráv (jednotky až desítky bajtů) zredukovat na výpočet množství přenášených zpráv. Každá fáze výpočtu má jiné komunikační nároky, proto rozebereme jednotlivé fáze zvlášť a výsledná komunikační náročnost bude součtem náročností jednotlivých fází. Protože v případě nalezení optimálního řešení se množství zpráv značně zredukuje, tak budeme uvažovat plný běh algoritmu včetně posílání peška a sběru výsledků.


\subsubsection*{Rozdělení práce}

Při rozdělování práce proces 0 rozešle zprávy s prací každému procesu vyjma sebe. Množství zpráv je tedy $p-1$.


\subsubsection*{Nová horní mez}

Nalezne-li proces řešení lepší než je dosavadní horní mez, tak pošle zprávu \texttt{TAG\us NEW\us UPPER\us BOUND}. Jeden oběžník je tedy $p-1$ zpráv. Nová horní mez může být nalezena během výpočtu m krát. Množství zpráv v této fázi je tedy $m(p-1)$.


\subsubsection*{Dynamické přidělování práce}

Dojde-li procesu práce, pak žádá nejvýše s-krát, kde s = max(\texttt{MAX\us WORK\us REQUESTS} = 5, $p-1$). Procesu dojde práce v průměru d-krát. Na každou žádost dostane proces odpověď. Nejvyšší celkové množství zpráv v této fázi je tedy $2pds$.


\subsubsection*{Ukončení výpočtu}

Ukončení výpočtu se se provádí posíláním peška v logickém kruhu. Neprojde-li pešek bílý napoprvé, pak se posílá znovu. Nejvyšší množství zpráv v této fázi je tedy $2p$.


\subsubsection*{Sběr výsledku}

Po přeposlání peška se v logickém kruhu posílá zpráva s řešením. Množství zpráv v této fázi je tedy $p$.


\subsubsection*{Celková komunikační náročnost}

Celkové množství zpráv je lineárně závislé na množství procesorů p, na hodnotě \texttt{MAX\us WORK\us REQUESTS} a na hodnotách d (kolikrát dojde procesu práce) a m (počet nalezených nových lepších řešení).

$z = p-1+m(p-1)+2pds+2p+p = p(4+2ds+m)$



\section*{Závěrečné zhodnocení a diskuse}

Shrňme zmíněné poznatky. Problém minimálního uzlového pokrytí grafu hledá minimální pod\-mno\-žinu uzlů $C$, která sousedí se všemi hranami grafu. Tento problém hledá kombinace uzlů (narozdíl od variací), díky této vlastnosti je strom stavového prostoru silně nevyvážený. Na základě znalosti tvaru tohoto stromu se dá ohodnotit množství uzlů v podstromu stavového prostoru, tedy jeho pracovní zátěž. Algoritmus staví na vcelku rovnoměrném rozdělení práce mezi procesy a na dynamické omezování hloubky prohledávání. Díky těmto vlastnostem má algoritmus nízkou komunikační náročnost a zároveň pro určité instance dosahuje superlineární zrychlení.   

Z naměřených hodnot můžeme vyvodit, že námi naimplementovaný algoritmus výpočtu minimálního uzlového pokrytí je velice dobře škálovatelný. Bohužel se nám nepodařilo naměřit z důvodu dlouhodobého přetížení fronty clusteru doby běhu pro větší počet procesorů.

Při analýze komunikační náročnosti algoritmu jsme objevili prostor ke zlepšení spojením zprávy o ukončení se zprávou sbírající nejlepší nalezené řešení. Tímto by se snížil počet zpráv z $p(4+2ds+m)$ na $p(3+2ds+m)$.

Za přínos vedle analýzy a řešení paralelního problému považujeme i nabyté zkušenosti programováním aplikací běžících na výpočetním clusteru pod frameworkem MPI.  

\end{document}



